﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <Windows.h>
//int main()
//{
//	int x = 0;
//	x = 5;
//	printf("x=%d\n", x);
//	system("pause");
//	return 0;
//}
// 请计算⼀下Func1中++count语句总共执⾏了多少次？
//void Func1(int N)
//{
//	int count = 0;
//	for (int i = 0; i < N; ++i)
//	{
//		for (int j = 0; j < N; ++j)
//		{
//			++count;
//		}
//	} 
//	for (int k = 0; k < 2 * N; ++k)
//	{
//		++count;
//	} 
//	int M = 10;
//	while (M--)
//	{
//		++count;
//	}
//}

// 计算Func2的时间复杂度？
//void Func2(int N)
//{
//	int count = 0;
//	for (int k = 0; k < 2 * N; ++k)
//	{
//		++count;
//	}
//	int M = 10;
//	while (M--)
//	{
//		++count;
//	}
//	printf("%d\n", count);
//}

// 计算Func3的时间复杂度？
//void Func3(int N, int M)
//{
//	int count = 0;
//	for (int k = 0; k < M; ++k)
//	{
//		++count;
//	}
//	for (int k = 0; k < N; ++
//		k)
//	{
//		++count;
//	}
//	printf("%d\n", count);
//}

// 计算Func4的时间复杂度？
//void Func4(int N)
//{
//	int count = 0;
//	for (int k = 0; k < 100; ++k)
//	{
//		++count;
//	} 
//	printf("%d\n", count);
//}

// 计算strchr的时间复杂度？
//const char* strchr(const char* str, int character)
//{
//	const char* p_begin = str;
//	while (*p_begin != character)
//	{
//		if(*p_begin == '\0')
//			return NULL;
//		p_begin++;
//	}
//	return p_begin;
//}


//int main()
//{
//	int x = 0;
//	x = 5;
//	printf("x=%d\n", x);
//	system("pause");
//	return 0;
//}

//#include <stdio.h>
//#define SUM 65535
//
//void main()
//{
//    int a, b = 20;
//    unsigned int c = 0xff;
//    long D;
//
//    a = SUM;
//    D = 301;
//    printf("a = %d\n", a);
//    printf("b = %d\n", b);
//    printf("c = %d\n", c);
//    printf("D = %d\n", D);
//}


//#define PRICE 30
//int main()
//{
//	int num = 0;
//	int total = 0;
//	num = 10;
//	total = num * PRICE;
//	printf("total = %d\n", total);
//	return 0;
//}

//// 计算BubbleSort的时间复杂度？
//void BubbleSort(int* a, int n)
//{
//	assert(a);
//	for (size_t end = n; end > 0; --end)
//	{
//		int exchange = 0;
//		for (size_t i = 1; i < end; ++i)
//		{
//			if (a[i - 1] > a[i])
//			{
//				Swap(&a[i - 1], &a[i]);
//				exchange = 1;
//			}
//		}
//		if (exchange == 0)
//			break;
//	}
//}


//// 计算Func4的时间复杂度？
//void func5(int n)
//{
//	int cnt = 1;
//	while (cnt < n)
//	{
//		cnt *= 2;
//	}
//}


//// 计算阶乘递归Fac的时间复杂度？
//long long Fac(size_t N)
//{
//	if (0 == N)
//		return 1;
//	return Fac(N - 1) * N;
//}

// 计算BubbleSort的空间复杂度？
//void BubbleSort(int* a, int n)
//{
//	assert(a);
//	for (size_t end = n; end > 0; --end)
//	{
//		int exchange = 0;
//		for (size_t i = 1; i < end; ++i)
//		{
//			if (a[i - 1] > a[i])
//			{
//				Swap(&a[i - 1], &a[i]);
//				exchange = 1;
//			}
//		}
//		if (exchange == 0)
//			break;
//	}
//}

//// 计算阶乘递归Fac的空间复杂度？
//long long Fac(size_t N)
//{
//	if (N == 0)
//		return 1;
//	return Fac(N - 1) * N;
//}

//思路1
//时间复杂度  O(n2)
//循环K次将数组所有元素向后移动⼀位（代码不通过）
//void rotate(int* nums, int numsSize, int k) {
//	while (k--)
//	{
//		int end = nums[numsSize - 1];
//		for (int i = numsSize - 1; i > 0; i--)
//		{
//			nums[i] = nums[i - 1];
//		} n
//			ums[0] = end;
//	}
//}

//空间复杂度  O(n)
//申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中
//void rotate(int* nums, int numsSize, int k)
//{
//	int newArr[numsSize];
//	for (int i = 0; i < numsSize; ++i)
//	{
//		newArr[(i + k) % numsSize] = nums[i];
//	} f
//		or (int i = 0; i < numsSize; ++i)
//	{
//		nums[i] = newArr[i];
//	}
//}

//空间复杂度  O(1)  • 前n - k个逆置：4 3 2 1 5 6 7
//• 后k个逆置   ：4 3 2 1 7 6 5
//• 整体逆置     ：5 6 7 1 2 3 4
//void reverse(int* nums, int begin, int end)
//{
//	while (begin < end) {
//		int tmp = nums[begin];
//		nums[begin] = nums[end];
//		nums[end] = tmp;
//		begin++;
//		end--;
//	}
//} v
//oid rotate(int* nums, int numsSize, int k)
//{
//	k = k % numsSize;
//	reverse(nums, 0, numsSize - k - 1);
//	reverse(nums, numsSize - k, numsSize - 1);
//	reverse(nums, 0, numsSize - 1);
//}\


//int newarr[size];
//for (int i = 0; i < size; i++)
//{
//	newarr[(i + k) % size] = arr[i];
//}
//for (int i = 0; i < size; i++)
//{
//	arr[i] = newarr[i];
//}

